排序總算來了～必備拆解思維邏輯才能掌握～

終於～～進入第一個排序演算法～～
白話來說快速排序就是「分割區交換」排序
就是將一組數據，從中通常抓第一個元素作為支點(pivot)，然後想辦法將比支點小的元素移動到支點元素的左邊，比支點大的元素移動到支點元素的右邊，接著再用同樣的方法繼續對支點的左邊子陣列和右邊子陣列進行排序～～

• 平均O(nlogn)時間複雜度/最壞（全部大小相反）情況O(n^2)時間複雜度
• 不穩定排序（相同元素的相對位置每次排序可能會不同）
• 分治法（Divide and Conquer）*

Step1: 選擇一個基準元素（pivot）
=> 假設有一個數列 [5, 1, 9, 3, 7, 6, 8, 2, 4]，我們選擇5作為基準
Step2: 遍歷 pivot 後所有小於基準的元素放左邊，大於基準的元素放右邊
=> 遍歷5後每個元素，小於5放左邊，大於等於5放右邊，得到 [1, 3, 2, 4, 5, 9, 7, 6, 8]
Step3: 對左右兩邊的子數列重複進行上述兩步操作
=> 對左右兩邊的子數列 [1, 3, 2, 4] 和 [9, 7, 6, 8] 重複進行上述兩步操作
Step4: 當子數列只有一個元素時，排序完成
=> 以此類推，直到每個子數列只剩一個元素不用排啦，排序完成

def quick_sort(arr):
    if len(arr) <= 1:
        #Step4: 當子數列只有一個元素時，排序完成
        return arr         
    else:
        #Step1: 選擇一個基準元素（pivot）
        pivot = arr[0]     
        left = []
        right = []
        #Step2: 遍歷 pivot 後所有小於基準的元素放左邊，大於基準的元素放右邊
        for x in arr[1:]:  
            if x < pivot:
                left.append(x)
            else:
                right.append(x)
        #Step3: 對左右兩邊的子數列重複進行上述兩步操作
        #此left + [pivot] + right為分治法（Divide and Conquer）
        return quick_sort(left) + [pivot] + quick_sort(right)  
        
        
raw_list = [5, 1, 9, 3, 7, 6, 8, 2, 4]
sorted_list = quick_sort(raw_list)
print(sorted_list)

分治法（Divide and Conquer）是一種常用的解決問題的算法設計策略三個步驟：

分解（Divide）：將原問題分解成若干個相同或相似的子問題。這些子問題通常是原問題的簡化版本。
解決（Conquer）：解決這些子問題，可以遞迴應用相同的方法。如果子問題足夠小，則直接求解。
合併（Combine）：將子問題的解合併成原問題的解。

• 快速排序（Quick Sort）：通過選擇一個基準元素，將數列分為兩部分，分別對左右兩部分進行排序。
  分解（Divide）：選擇一個基準元素，將數列分為兩部分，左邊部分的元素小於基準，右邊部分的元素大於等於基準。
  解決（Conquer）：對左右兩部分分別遞迴地應用相同的方法。
  合併（Combine）：無需額外合併步驟，因為排序已經完成。
• 合併排序（Merge Sort）：將數列分為多個子序列，分別對這些子序列進行排序，然後將已排序的子序列合併。
• 二分搜索（Binary Search）：將有序數列一分為二，然後確定目標值可能存在的區間，逐步縮小範圍。
• 最接近點對問題：在平面上給定n個點，找到最接近的兩個點。
• 求解凸多邊形的最小周長：將凸多邊形分為兩半，分別求解左半部分和右半部分的最小周長，然後比較。
• 求解凸多邊形的最大面積：將凸多邊形分為兩半，分別求解左半部分和右半部分的最大面積，然後比較。